# This is a sample Python script.

# Press Shift+F10 to execute it or replace it with your code.
# Press Double Shift to search everywhere for classes, files, tool windows, actions, and settings.
import time

from Board import Board
from Position import Position

open_list = []
close_list = []


def IsInBoard(i, j):
    if 0 <= i < len(mapp) and len(mapp[i]) > j >= 0 == mapp[i][j]:
        return 1
    else:
        return 0


def SearchPath(mapp, cp, target_position):
    start_time = time.time()  # 计时
    board = Board(mapp, target_position)  # 地图棋盘对象
    board.GetMsg(cp).IsUnk = 0
    open_list.append(cp)
    while open_list != []:
        # for k in range(len(board.mapx)):
        #     for m in range(len(board.mapx[k])):
        #         if(board.mapx[k][m].parent):
        #             print('p',board.mapx[k][m].parent.__dict__,end=" ")
        #         else: print('p',"                ",end=" ")
        #     print('')
        # print('')
        # 取出第一个（F最小，判定最优）位置
        current_position = open_list[0]
        open_list.remove(current_position)
        # close_list.append(current_position)
        # 到达
        if current_position == target_position:
            print("成功找到解")
            tmp = []  # 内存储Position
            while current_position is not None:
                tmp.append(current_position)
                current_position = board.GetMsg(current_position).parent
            tmp.reverse()
            for i in tmp:
                print(str(i.__dict__))
            end_time = time.time()  # 计时
            print(end_time - start_time)
            return

        # 将下一步可到达的位置加入open_list，并检查记录的最短路径G是否需要更新，记录最短路径经过的上一个点
        # 斜（上下左右与此思路相同，只是细节有差）
        # for i in [current_position.x - 1, current_position.x + 1]:
        #     for j in [current_position.y - 1, current_position.y + 1]:
        #         if IsInBoard(i, j):
        #             new_G = board.GetMsg(current_position).G + 14
        #             # 维护当前已知最短G
        #             if board.mapx[i][j].IsUnk:
        #                 board.mapx[i][j].IsUnk = 0
        #                 open_list.append(Position(i, j))
        #                 board.mapx[i][j].parent = current_position
        #                 board.mapx[i][j].G = new_G
        #
        #             if board.mapx[i][j].G > new_G:  # 如果未遍历或需更新
        #                 board.mapx[i][j].parent = current_position
        #                 board.mapx[i][j].G = new_G
        # 上下
        j = current_position.y
        for i in [current_position.x - 1, current_position.x + 1]:
            if IsInBoard(i, j):
                new_G = board.GetMsg(current_position).G + 10
                if board.mapx[i][j].IsUnk:
                    board.mapx[i][j].IsUnk = 0
                    open_list.append(Position(i, j))
                    board.mapx[i][j].parent = current_position
                    board.mapx[i][j].G = new_G

                if board.mapx[i][j].G > new_G:  # 如果未遍历或需更新
                    board.mapx[i][j].parent = current_position
                    board.mapx[i][j].G = new_G
        # 左右
        i = current_position.x
        for j in [current_position.y - 1, current_position.y + 1]:
            if IsInBoard(i, j):
                new_G = board.GetMsg(current_position).G + 10
                if board.mapx[i][j].IsUnk:
                    board.mapx[i][j].IsUnk = 0
                    open_list.append(Position(i, j))
                    board.mapx[i][j].parent = current_position
                    board.mapx[i][j].G = new_G

                if board.mapx[i][j].G > new_G:  # 如果未遍历或需更新
                    board.mapx[i][j].parent = current_position
                    board.mapx[i][j].G = new_G
        # open_list.sort(key=searchKey(board))
        # 对open_list里的内容按F的大小排序
        open_list.sort(key=lambda elem: board.GetMsg(elem).GetF())


if __name__ == "__main__":
    # 定义初始状态
    mapp = [[0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
            [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]]

    start_position = Position(4, 0)
    target_position = Position(0, 6)
    SearchPath(mapp, start_position, target_position)

# See PyCharm help at https://www.jetbrains.com/help/pycharm/
